/*
公司共有 n 个项目和  m 个小组，每个项目要不无人接手，要不就由 m 个小组之一负责。

group[i] 表示第 i 个项目所属的小组，如果这个项目目前无人接手，那么 group[i] 就等于 -1。（项目和小组都是从零开始编号的）小组可能存在没有接手任何项目的情况。

请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：

同一小组的项目，排序后在列表中彼此相邻。
项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 beforeItems[i] 表示在进行第 i 个项目前（位于第 i 个项目左侧）应该完成的所有项目。
如果存在多个解决方案，只需要返回其中任意一个即可。如果没有合适的解决方案，就请返回一个 空列表 。


示例 1：
Item  Group  Before
   0     -1
   1     -1       6
   2      1       5
   3      0       6
   4      0     3,6
   5      1
   6      0
   7     -1

输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
输出：[6,3,4,1,5,2,0,7]
示例 2：

输入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]]
输出：[]
解释：与示例 1 大致相同，但是在排序后的列表中，4 必须放在 6 的前面。
 

提示：

1 <= m <= n <= 3 * 104
group.length == beforeItems.length == n
-1 <= group[i] <= m - 1
0 <= beforeItems[i].length <= n - 1
0 <= beforeItems[i][j] <= n - 1
i != beforeItems[i][j]
beforeItems[i] 不含重复元素

*/

#include "stdc++.h"

/* 拓扑排序

做出这道题首先需要了解「拓扑排序」的相关知识。

拓扑排序简单来说，是对于一张有向图 G，我们需要将 G 的 n 个点排列成一组序列，使得图中任意一对顶点 <u,v>，如果图中存在一条 u→v 的边，那么 u 在序列中需要出现在 v 的前面。

整个算法的具体过程这里不再展开赘述。如果对相关的知识还不是很熟悉，可以参考「207. 课程表的官方题解」。

回到题目中，我们可以将项目抽象成点，项目间依赖关系的抽象成边，即如果进行项目 i 前需要完成项目 j，那么就存在一条 j→i 的边。然后判断图中是否可以拓扑排序。

但这样的方法忽略了题目中的一个关键条件：「同一小组的项目，排序后在列表中彼此相邻」。这意味着组与组之间也存在依赖关系，故还要解决组之间的拓扑排序。

基于此，解决这道题其实可以分成两步：

首先解决组与组的依赖关系。我们将组抽象成点，组与组的关系抽象成边，建图后判断是否存在一个拓扑排序。
如果存在拓扑顺序 groupTopSort，我们只要再确定组内的依赖关系。遍历组间的拓扑序 groupTopSort，对于任意的组 g，对所有属于组 g 的点再进行拓扑排序。如果能够拓扑排序，则将组 g 内部的拓扑序按顺序放入答案数组即可。
实现细节

注意到某些项目存在无人接手的情况，由于这些 groupId 都为 −1，为了编码方便，我们重新将其编号。由于已有的小组编号不会超过 m−1，因此可以将这些项目从 m 开始正序编号，这样能保证不会与已存在的小组编号冲突。

为了减少编码的复杂度，我们可以将拓扑排序抽成一个函数进行复用，定义 topSort(deg, graph, items) 
表示当前待拓扑排序的点集为 items，点的入度数组为 deg，点的连边关系为 graph，graph[i] 表示点 i 连出点组成的集合，如果不存在冲突，返回拓扑排序后的数组，否则返回一个空数组。

在建图的过程中，如果发现两个项目属于不同的项目组，则在组间的关系图中添加对应的边，否则在组内的关系图中添加对应的边。编码细节请看下面的代码。

*/
class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        vector<vector<int>> groupItem(n + m);

        vector<vector<int>> groupGraph(n + m); // 组间依赖图
        vector<vector<int>> itemGraph(n);      // 组内依赖图

        vector<int> groupDegree(n + m, 0);     // 组间入度数组
        vector<int> itemDegree(n, 0);          // 组内入度数组

        vector<int> id(n + m, 0);
        for (int i{0}; i < n + m; ++i) {
            id[i] = i;
        }

        int leftId = m;
        for (int i{0}; i < n; ++i) {
            if (group[i] == -1) {
                group[i] = leftId++; // 给未分配的item分配一个groupId，从m开始
            }
            groupItem[group[i]].emplace_back(i); // 分组
        }

        // 依赖关系建图
        for (int i{0}; i < n; ++i) {
            int curGroupId = group[i];
            for (auto& item : beforeItems[i]) {
                int beforeGroupId = group[item];
                if (beforeGroupId == curGroupId) { // 组内
                    itemDegree[i] += 1;
                    itemGraph[item].emplace_back(i);
                } else { // 组间
                    groupDegree[curGroupId] += 1;
                    groupGraph[beforeGroupId].emplace_back(curGroupId);
                }
            }
        }

        // 组间拓扑关系排序
        vector<int> groupTopSort = topSort(groupDegree, groupGraph, id);
        if (groupTopSort.size() == 0) {
            return {}; // 排序失败，没有合适的排序结果
        }

        vector<int> ret{};
        // 按组间排序的顺序在各个组内部进行组内拓扑排序
        for (auto& curGroupId : groupTopSort) {
            int size = groupItem[curGroupId].size();
            if (size == 0) {
                continue;
            }
            // 组内拓扑关系排序
            vector<int> itemTopSort = topSort(itemDegree, itemGraph, groupItem[curGroupId]);
            if (itemTopSort.size() == 0) {
                return {}; // 排序失败，没有合适的排序结果
            }
            for (auto& item : itemTopSort) {
                ret.emplace_back(item);
            }
        }
        return ret;
    }
    vector<int> topSort(vector<int>& degree, vector<vector<int>>& graph, vector<int>& items) {
        queue<int> q{};
        for (auto& item : items) {
            if (degree[item] == 0) {
                q.push(item); // 入度为0的为起点
            }
        }
        vector<int> ret{};
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            ret.emplace_back(u);
            // 把所有的u的邻点的入度减一
            for (auto& v : graph[u]) {
                if (--degree[v] == 0) {
                    q.push(v);
                }
            }
        }
        return ret.size() == items.size() ? ret : {};
    }
};